package D.队列;

import java.util.LinkedList;
import java.util.Queue;

public class _剑指Offer59_滑动窗口的最大值 {
    public int[] maxSlidingWindow(int[] nums, int k) {

        if (nums.length==0){
            return nums;
        }

        Queue<Integer> queue = new LinkedList<>();
        int max = Integer.MIN_VALUE;
        int[] result = new int[nums.length-k+1];
        int index=0;
        //没有窗口
        for (int i=0;i<k;i++){
            queue.add(nums[i]);
            max = max<nums[i]?nums[i]:max;
        }
        result[index++] = max;

        if (index<=nums.length-k+1){
            for (int i=k;i < nums.length;i++){
                int cur = queue.poll();
                queue.add(nums[i]);
                //弹出的是不是max值
                if (cur == max){
                    //重新计算max
                    max = nums[i];
                    for (int j:queue){
                        if (j>=nums[i]){
                            max = j;
                        }
                    }
                }else{
                    //不是max 就用max和num比较
                    if (max <= nums[i]){
                        max =nums[i];
                    }
                }
                result[index++] = max;
            }
        }

        return result;
    }

    /**
     * 题解 借助最小栈那道题的思想 将队列看作是非递增的队列 只要来一个更大的 就把前面小的poll出去
     * 代码不好写
     */

}
